class Solution(object):
    def minDeletionSize(self, strs):
        n = len(strs)
        m = len(strs[0])

        def cmp(s1, s2):
            c = 0
            for i in range(n):
                if s1[i] <= s2[i]:
                    c += 1
            if c == n:
                return -1
            if c == 0:
                return 1
            return 0

        st = [{''.join([strs[i][0] for i in range(n)])}]
        for i in range(1, m):
            t = len(st)
            now_s = ''.join([strs[j][i] for j in range(n)])
            for i in range(t - 1, -1, -1):
                now_set = st[i]
                index = 0
                for node in now_set:
                    val = cmp(node, now_s)
                    if val == -1:
                        index = i + 1
                        break
                    if val == 1:
                        break
                if index > 0:
                    break
            if index >= 0:
                if index == len(st):
                    st.append({now_s})
                else:
                    pop_node = set()
                    for node in st[index]:
                        if cmp(node, now_s) == 1:
                            pop_node.add(node)
                    st[index] -= pop_node
                    st[index].add(now_s)
        return m - len(st)


data = Solution()
strs = ["aabbaa", "baabab", "aaabab"]
print(data.minDeletionSize(strs))
